#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int maxValue(vector<int> weight, vector<int> p, int W)
    {
        vector<vector<int>> dp(weight.size(), vector<int>(W+1, 0));
        for(int j = W+1; j-weight[0]>=0; j--)
        {
            dp[0][j] = max(dp[0][j], dp[0][j-weight[0]]+p[0]);
        }
        for(int i = 1; i <weight.size(); i++)
        {
            for(int j = 1; j < W+1; j++)
            {
                if(j-weight[i]>0)
                {
                    dp[i][j] = max(dp[i-1][j-weight[i]]+p[i], dp[i-1][j]);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[weight.size()-1][W];
    }
};

int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> weight(N, 0);
    vector<int> p(N, 0);
    for(int i = 0; i < N; i++)
    {
        cin >> weight[i] >> p[i];
    }
    Solution sol;
    cout << sol.maxValue(weight, p, W) << endl;
}